P2480 [SDOI2010]古代猪文

发布于 2020-09-12 | 分类于数论 | 4分钟 | 515字数

g^{\sum_{d|n}C_{n}^{n/d}} \mod 999911659

g^{\sum_{d|n}C_{n}^{d}} \mod 999911659

P5769 [JSOI2016]飞机调度

发布于 2020-09-12 | 分类于网络流 | 5分钟 | 758字数

网络流24题为了使飞机数量尽量少，一架飞机尽量多飞几趟航班。将航班看成一个点，其实就是求最小路径覆盖。

发布于 2020-09-12 | 分类于数论、欧拉函数 | 2分钟 | 266字数

\sum_{i=1}^n(i,n)

\sum_{d|n}d\sum_{i=1}^n[(i,n)=d]

发布于 2020-09-12 | 分类于数论、欧拉函数 | 6分钟 | 967字数

因为每回合击中的概率是固定的，所以只需要算一次。概率为：可以击中的情况/总情况。每个点有

(n+1)^2

个位置，所以总情况为

(n+1)^4

发布于 2020-09-12 | 分类于莫比乌斯反演 | 3分钟 | 417字数

如果你做过 P4358 [CQOI2016]密钥破解，那么你基本上就凉了。

这道题跟背景没有任何关系。

注意到二元不定方程： $xe1+ye2=(e1,e2)=1$

发布于 2020-09-12 | 分类于莫比乌斯反演 | 5分钟 | 758字数

\sum_{i=1}^n\sum_{j=1}^m \sigma((i,j))

\sum_{d=1}^{\min(n,m)}\sigma(d)\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=d]

发布于 2020-09-12 | 分类于数论、欧拉函数 | 1分钟 | 141字数

观察样例可以发现：

发布于 2020-09-12 | 分类于莫比乌斯反演 | 3分钟 | 471字数

这道题的反推还是挺有意思的。

\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor \frac{n}{j} \rfloor}\sum_{q=1}^{\lfloor \frac{n}{j} \rfloor}[(i,j)=1][(p,q)=1]

发布于 2020-09-12 | 分类于树形dp | 4分钟 | 750字数

此题有一个神仙结论：最优链上最多包含一个‘2’，且‘2’不能在链的两边。 至于证明过于简单但很麻烦（~~其实是我懒~~），给大家推荐一个博客，点这。

有了这个结论之后，我们就可以愉快的开始树形dp了。

发布于 2020-09-12 | 6分钟 | 905字数

\sum_{i=1}^n\sum_{j=1}^m ij (i,j)\mu^2((i,j))

\sum_{k=1}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m [(i,j)=k]ij k\mu^2(k)